package divide_and_conquer;

import java.util.Stack;

//https://leetcode.cn/leetbook/read/illustration-of-algorithm/5vwxx5/
//请实现一个函数来判断整数数组 postorder 是否为二叉搜索树的后序遍历结果。
public class LCR_152验证二叉搜索树的后序遍历序列 {
    //递归分治
    class Solution {
        public boolean verifyTreeOrder(int[] postorder) {
            return recur(postorder, 0, postorder.length - 1);
        }
        boolean recur(int[] postorder, int i, int j) {
            if(i >= j) return true;
            int p = i;
            while (postorder[p] < postorder[j]) p++;
            int m = p; //左右子树的分界线
            while (postorder[p] > postorder[j]) p++;
            return p==j && recur(postorder,i,m-1) && recur(postorder,m,j-1);//j是根节点
        }
    }
    //辅助单调栈
    class Solution2 {
        public boolean verifyTreeOrder(int[] postorder) {
            Stack<Integer> stack = new Stack<>();
            int root = Integer.MAX_VALUE;
            for(int i = postorder.length-1; i>=0; i--){
                if(postorder[i] > root) return false;
                while (!stack.isEmpty() && stack.peek() > postorder[i])
                    root = stack.pop();
                stack.add(postorder[i]);
            }
            return  true;
        }
    }
}
